package LinkedList;



//用Java创建一个链表，并且寻找链表的倒数第N个节点。
public class FindNthFromEnd {
        // 定义一个节点
        private static class Node{
            int data;
            Node next;

            public Node(int data) {
                this.data = data;
            }
        }
        //创建链表
        private static Node Build(int[] array){
            Node head=new Node(array[0]);
            Node p=head;
            for (int i = 1; i < array.length ; i++) {
                p.next=new Node(array[i]);
                p=p.next;
            }
            return head;
        }
        //寻找倒数第n个节点
        public static Node FindNthFromEnd(Node head,int n){
            Node p1=head;
            Node p2=head;
            for (int i = 1; i <n ; i++) {
                p1=p1.next;
                if (p1==null){
                    throw new IllegalArgumentException("Over the length of array!");
                }
            }
            while (p1.next!=null){
                p1=p1.next;
                p2=p2.next;
            }
            return p2;
        }

    public static void main(String[] args) {
        int[] array={1,2,5,6,3,6};
        Node head = FindNthFromEnd.Build(array);
        Node node = FindNthFromEnd.FindNthFromEnd(head, 3);
        System.out.println(node.data);
    }
}
